from typing import List


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        n = len(hours)
        s = [0] * (n + 1)  # 前缀和
        st = [0]  # s[0]  初始化 栈顶为0，前缀和为0，等价于，劳累天数大于不劳累天数
        # 解释，为什么栈顶为0，维护单调递减栈
        # 因为  大于8小时 赋值为1 小于等于8小时的赋值为-1， 前缀和为 >0，说明满足题目要求 表现良好
        # 以0 为 栈顶，维护递减单调栈。前缀和运算过程中，会被递减到0，再运算会到-1，把-1 入栈，则前缀和运算到-1 时，前缀和 大于 -1 的一定是 表现良好的区间，运行到-2 同理
        # 右遍历前缀和，只要大于 栈顶元素的 就是一个表现良好区间
        for j, h in enumerate(hours, 1):
            s[j] = s[j - 1] + (1 if h > 8 else -1)
            if s[j] < s[st[-1]]:
                # 维护 一个 单调递减的 栈
                st.append(j)  # 感兴趣的 j
        ans = 0
        # 倒叙遍历
        for i in range(n, 0, -1):
            while st and s[i] > s[st[-1]]:
                ans = max(ans, i - st.pop())  # [st[-1],i) 可能是最长子数组
        return ans